package common;

import BinarySearch.BinarySearch;

import java.util.Arrays;

/**
 * @ClassName: TwoSumFast
 * @Description: 2-sum问题的线性对数级别的解法
 * @Date: 2021/2/22
 * @Author: cakin
 */
public class TwoSumFast {
    /**
     * 功能描述：计算和为0的整数对的数目
     *
     * @param a 数组
     * @return 和为0的个数
     * @author cakin
     * @date 2021/2/22
     */
    public static int count(int[] a) {
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (BinarySearch.indexOf(a, -a[i]) > i) {
                cnt++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int[] a = in.readAllInts();

        Stopwatch timer = new Stopwatch();
        int count = count(a);
        StdOut.println("elapsed time = " + timer.elapsedTime());
        StdOut.println(count);
    }
}
